package wire

import (
	"container/heap"
	"errors"
	"fmt"
	"reflect"
)

// Void is a type used to represent the return type
// of a function with no output parameters.
type Void struct{}

// Void represents no value.
var VoidValue Void

// VoidFunc is a Func that can be used to throw away
// a value. It takes a single argument of type Void
// and returns nothing.
var VoidFunc = NewFunc(func(struct{}, Void) {})

// A Converter is a function that can convert from
// one given type to another. When called, src
// is the value to be converted, and dst is an settable
// value that points to the destination.
//
type Converter func(src, dst reflect.Value) error

// Conversions represents a set of possible type conversions.
type Conversions interface {
	// Converter returns a Converter function that
	// will convert from type src to type dst.
	Converter(src, dst reflect.Type) Converter
}

// identity implements the null conversion. It simply stores src into dst.
func identity(src, dst reflect.Value) error {
	dst.Set(src)
	return nil
}

type naiveConversions struct{}

func (naiveConversions) Converter(src, dst reflect.Type) Converter {
	if src.AssignableTo(dst) {
		return identity
	}
	return nil
}

type GraphConversions struct {
	nodes map[reflect.Type]*node
}

func NewGraphConversions() *GraphConversions {
	return &GraphConversions{make(map[reflect.Type]*node)}
}

// A mark holds data about a node when we are doing
// a shortest path calculation. It is stored separately
// to its associated node so that we can do several shortest path
// calculations in parallel if we wish.
type mark struct {
	node     *node // node that this mark is on.
	dist     int   // total distance to this node.
	dups     int   // count of duplicate path lengths.
	previous *mark // previous node in the shortest path.
	arc      *arc  // arc between here and previous.
	index    int   // index into markHeap
}

// node represents one node in the type graph.
// The slice of arcs lead from it to other types via
// conversion operators.
type node struct {
	t   reflect.Type
	arc []*arc
}

// arc represents a possible conversion between two types.
type arc struct {
	cvt  Converter
	dst  *node
	name string
}

// find shortest path between two types using Dijstra's algorithm.
func (g *GraphConversions) shortestPath(src, dst reflect.Type) *mark {
	n0 := g.nodes[src]
	n1 := g.nodes[dst]
	if n0 == nil || n1 == nil {
		return nil
	}
	q := markHeap{&mark{node: n0, dist: 0}}

	// marks associates a mark with each node that we have considered.
	marks := map[*node]*mark{n0: q[0]}

	// loop while there are connected nodes to consider.
	for len(q) > 0 {
		// consider the node that is closest to the source node
		// (due to the heap invariant, this is always at index 0).
		u := q[0]
		if u.node == n1 {
			return u
		}
		heap.Remove(&q, 0)

		// look at each arc from the node we are considering
		for _, a := range u.node.arc {
			//fmt.Printf("consider %v->%v\n", u.node.t, a.dst.t)
			if v := marks[a.dst]; v != nil {
				// if we have found a node via a shorter route,
				// we reposition it in the heap and reset
				// any duplicate paths to it.
				if u.dist+1 < v.dist {
					heap.Remove(&q, v.index)
					v.dist = u.dist + 1
					//fmt.Printf("shorter %v, new dist %d\n", v.node.t, v.dist)
					//if v.dups > 0 {
					//	fmt.Printf("resetting dups (was %d) on %v\n", v.dups, v.node.t)
					//}
					v.dups = 0
					v.arc = a
					v.previous = u
					heap.Push(&q, v)
				} else if u.dist+1 == v.dist {
					// if the current route is the same length as the
					// old (shortest so far) route, then we have
					// a duplicate path, which may be a duplicate
					// shortest path if this node lies on the final
					// shortest path.
					v.dups++
					//fmt.Printf("possible dup on %v (dist %d), from %v\n", v.node.t, v.dist, u.node.t)
				}
			} else {
				v := &mark{node: a.dst, dist: u.dist + 1, previous: u, arc: a}
				//fmt.Printf("add %v, dist %d, from %v\n", v.node.t, u.dist+1, u.node.t)
				heap.Push(&q, v)
				marks[a.dst] = v
			}
		}
	}
	return nil
}

// duplicatePath returns a non-nil mark if there
// is there is more than one shortest path between
// any two nodes in the conversion graph.
// The returned mark is one of the duplicate paths.
func (g *GraphConversions) duplicatePath() *mark {
	// find duplicate path by finding shortest path
	// between all nodes and seeing if any have
	// duplicate lengths.
	for t0 := range g.nodes {
		for t1 := range g.nodes {
			if t0 == t1 {
				continue
			}
			//fmt.Printf("shortest path from %v to %v\n", t0, t1)
			//n := 0
			p := g.shortestPath(t1, t0)
			for m := p; m != nil; m = m.previous {
				if m.dups > 0 {
					//fmt.Printf("found dup at %v\n", m.node.t)
					return p
				}
				//n++
			}
			//fmt.Printf("len %d\n", n)
		}
	}
	return nil
}

func (g *GraphConversions) Converter(src, dst reflect.Type) Converter {
	if src == dst {
		return identity
	}
	m := g.shortestPath(src, dst)
	if m == nil {
		return nil
	}
	//fmt.Printf("conversion from %v -> %v\n", src, dst)
	//fmt.Printf("\t%s\n", pathString(m))
	for l := m; l.previous != nil; l = l.previous {
		if l.dups > 0 {
			panic("duplicate path!")
		}
	}
	return newConverter(m)
}

func newConverter(m *mark) Converter {
	if m.previous.previous == nil {
		return func(src, dst reflect.Value) error {
			return m.arc.cvt(src, dst)
		}
	}
	cvt := newConverter(m.previous)
	return func(src, dst reflect.Value) error {
		tmp := reflect.New(m.previous.node.t).Elem()
		if err := cvt(src, tmp); err != nil {
			return err
		}
		if err := m.arc.cvt(tmp, dst); err != nil {
			return err
		}
		return nil
	}
}

func pathString(p *mark) string {
	if p.previous == nil {
		return p.node.t.String()
	}
	return pathString(p.previous) + "->(" + p.arc.name + ")->" + p.node.t.String()
}

func (g *GraphConversions) AddFunc(src, dst reflect.Type, f *Func, name string) error {
	if f.t.NumIn() != 1 {
		return errors.New("func requires a single argument")
	}
	if f.t.In(0).actualType != src {
		return fmt.Errorf("incorrect type for func argument, expected %v got %v", src, f.t.In(0).actualType)
	}
	if f.t.Out().actualType != dst {
		return fmt.Errorf("incorrect type for func return, expected %v got %v", dst, f.t.Out().actualType)
	}
	cvt := func(src, dst reflect.Value) error {
		return f.Call(naiveConversions{}, dst.Addr().Interface(), nil, src.Interface())
	}
	return g.Add(src, dst, cvt, name)
}

// Add adds a new possible conversion from src to dst,
// using cvt. The given name is used for informational purposes only.
// It returns an error if the conversion causes an ambiguity.
func (g *GraphConversions) Add(src, dst reflect.Type, cvt Converter, name string) error {
	n0 := g.nodes[src]
	addn0 := n0 == nil
	if addn0 {
		n0 = &node{t: src}
		g.nodes[src] = n0
	}
	n1 := g.nodes[dst]
	addn1 := n1 == nil
	if addn1 {
		n1 = &node{t: dst}
		g.nodes[dst] = n1
	}
	n0.arc = append(n0.arc, &arc{cvt, n1, name})

	if p1 := g.duplicatePath(); p1 != nil {
		// remove added arc
		n0.arc = n0.arc[0 : len(n0.arc)-1]

		// remove new nodes if they were added
		if addn0 {
			delete(g.nodes, src)
		}
		if addn1 {
			delete(g.nodes, dst)
		}

		// find start of duplicate path
		p0 := p1
		for p0.previous != nil {
			p0 = p0.previous
		}
		oldp := g.shortestPath(p0.node.t, p1.node.t)
		if oldp == nil {
			panic(fmt.Errorf("duplicate path but no path previously (%v)", p1))
		}

		// TODO say what the duplicate path is
		return fmt.Errorf("duplicate of conversion path {%v} when adding %q {%v->%v}", pathString(oldp), name, src, dst)
	}
	return nil
}

// heap of marked nodes, for use with Dijkstra's algorithm.
type markHeap []*mark

func (h *markHeap) Len() int {
	return len(*h)
}

func (h *markHeap) Less(i, j int) bool {
	a := *h
	return a[i].dist < a[j].dist
}

func (h *markHeap) Swap(i, j int) {
	a := *h
	a[i], a[j] = a[j], a[i]
	a[i].index = i
	a[j].index = j
}

func (h *markHeap) Push(x interface{}) {
	m := x.(*mark)
	a := *h
	m.index = len(a)
	*h = append(a, m)
}

func (h *markHeap) Pop() interface{} {
	a := *h
	x := a[len(a)-1]
	*h = a[0 : len(a)-1]
	x.index = -1
	return x
}
